package ch2.part3;

import ch2.part2.MyLinkedList;

/**
 * 栈的数据结构 - 链表实现
 * 时间复杂度：
 * - 入栈：O(n)=1
 * - 出栈：O(n)=1
 *
 * @author liuwanxiang
 * @version 2019/05/14
 */
public class MyLinkedStack {

    private MyLinkedList innerStack;
    private int pointer;
    private int depth;

    public MyLinkedStack(int depth) {
        this.depth = depth;
        this.pointer = -1;
        this.innerStack = new MyLinkedList();
    }

    /**
     * 入栈
     * 时间复杂度：O(n)=1
     *
     * @param data
     */
    public void push(Integer data) {
        if (pointer >= depth - 1) {
            throw new RuntimeException("栈溢出~");
        }
        innerStack.insert(++pointer, data);
    }

    /**
     * 出栈
     * 时间复杂度：O(n)=1
     *
     * @return
     */
    public Integer pop() {
        if (pointer < 0) {
            throw new RuntimeException("栈空~");
        }
        return innerStack.delete(pointer--);
    }

    public static void main(String[] args) {

        MyLinkedStack stack = new MyLinkedStack(3);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }

}
